package leetcode.newcoder;

import java.util.*;

/**
 * Created by tiang on 2018/7/24.
 * 题目描述
 某餐馆有n张桌子，每张桌子有一个参数：a 可容纳的最大人数； 有m批客人，每批客人有两个参数:b人数，c预计消费金额。
 在不允许拼桌的情况下，请实现一个算法选择其中一部分客人，使得总预计消费金额最大
 输入描述:
 输入包括m+2行。 第一行两个整数n(1 <= n <= 50000),m(1 <= m <= 50000) 第二行为n个参数a,
 即每个桌子可容纳的最大人数,以空格分隔,范围均在32位int范围内。 接下来m行，每行两个参数b,c。
 分别表示第i批客人的人数和预计消费金额,以空格分隔,范围均在32位int范围内。
 输出描述:
 输出一个整数,表示最大的总预计消费金额
 输入：
 3 5 2 4 2 1 3 3 5 3 7 5 9 1 10
 输出：
 20
 */
public class MostPay {
    /**
     * 仔细分析了一下这道题，感觉像是可以用动态规划做但是又找不到递推公式
     * 一开始采用暴力破解：
     * 1. 遍历每一个桌子
     * 2. 寻找能适合这个桌子的最合适的团体，即金额最大的情况下人数最多的团体
     * 3. 将这个团体标记为已安排
     * 这样的效率是o(n*m)，尽管采取了一定的优化措施，
     *   将团体按照人数从小到大排序，遍历到团体人数大于这个桌子的时候就表示已经不存在更合适这张桌子的团体了，进而去安排下一张桌子
     *   但是总体的时间复杂度仍然是o(n*m)，最终会超时。
     *   getMaxPay1和getMaxPay2都是采用这种思想，结果超时了
     *
     * 后来在论坛上看到一种方法：
     * 1. 先将桌子按从小到大的顺序排序
     * 2. 将团体按照金额从大到小排列
     * 3. 遍历每一个团体，为这个团体安排最合适的桌子。即桌子的容量大于且最接近团体的人数。
     *    这里遍历桌子就只有一个容量变量，所以可以采用二分查找来提高效率，从而使整体的时间复杂度减少为o(m*log2(n))
     * getMaxPay方法采用了这种思想
     *
     * 总结一下，这个方法的复杂度只是稍微降低了一点，将较为简单的查找放在内层循环而且使用二分查找
     */
    static class Pair implements Comparable{
        public int b, c;
        public Pair(int x, int y){
            this.b = x;
            this.c = y;
        }

        @Override
        public int compareTo(Object o) {
            Pair temp = (Pair)o;
            return this.b - temp.b;
            /*int div = temp.b - this.b;
            if(div == 0)
                return temp.c - this.c;
            else
                return div;*/
        }
    }
    public static long getMaxPay1(int[] tables, Pair[] people){
        Arrays.sort(people);
        boolean[] used = new boolean[people.length];
        long result = 0;
        for(int i=0;i<tables.length;i++){
            int tableResult = 0;
            int lastIndex = -1;
            for(int j=0;j<people.length;j++){
                if(!used[j] && people[j].b<=tables[i]){
                    if(people[j].c > tableResult || people[j].c == tableResult &&people[j].b>people[lastIndex].b) {
                        if (lastIndex != -1)
                            used[lastIndex] = false;
                        used[j] = true;
                        lastIndex = j;
                        tableResult = people[j].c;
                    }
                }else if(people[j].b > tables[i])
                    break;
            }
            result += tableResult;
        }
        return result;
    }

    public static long getMaxPay2(int[] tables, TreeMap<Integer, List<Integer>> people){
        for(int key : people.keySet()){
            people.get(key).sort((i1, i2)->i2-i1);
        }
        Arrays.sort(tables);
        long result = 0;
        for(int i=0;i<tables.length;i++){
            int lastKey = -1;
            int lastValue = 0;
            for(int key : people.keySet()){
                if(key>tables[i])
                    break;
                List<Integer> temp = people.get(key);
                if(temp.size() == 0) {
                    continue;
                }
                if(temp.get(0)>=lastValue){
                    if(lastKey!=-1){
                        people.get(lastKey).add(0, lastValue);
                    }
                    lastKey = key;
                    lastValue = people.get(key).get(0);
                    temp.remove(0);
                }
            }
            result += lastValue;
        }
        return result;
    }

    public static long getMaxPay(List<Integer> tables, List<Pair> people){
        // 桌号从小到大排列
        tables.sort(Integer::compareTo);
        // 团体按消费金额从大到小排列
        people.sort((p1, p2)->p2.c-p1.c);
        long result = 0;
        for(int i=0;i<people.size();i++){
            // 如果人数比最大的桌子的容量还大就跳过
            if(people.get(i).b>tables.get(tables.size()-1))
                continue;
            int tableNum = findTheMostSuitableTable(tables, people.get(i).b);
            result += people.get(i).c;
            tables.remove(tableNum);
            if(tables.size() == 0)
                break;
        }
        return result;
    }

    /**
     * 找到人数最合适的桌子号，采用二分查找
     * @param tables
     * @param peopleCount
     * @return
     */
    private static int findTheMostSuitableTable(List<Integer> tables, int peopleCount){
        int left = 0,
                right = tables.size();
        while(left<right) {
            int middle = (left+right)/2;
            if (peopleCount > tables.get(middle)) {
                left = middle+1;
            }else{
                right = middle-1;
            }
        }
        return tables.get(left) < peopleCount?left+1:left;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<Integer> tables = new ArrayList<>();
        for(int i=0;i<n;i++)
            tables.add(scanner.nextInt());
        List<Pair> people = new ArrayList<>();
        for(int i=0;i<m;i++)
            people.add(new Pair(scanner.nextInt(), scanner.nextInt()));
        long result = getMaxPay(tables, people);
        System.out.println(result);
    }
}
